//https://leetcode.cn/problems/course-schedule/

// class Solution {
// public:
//     vector<vector<int>> v;
//     vector<vector<int>> ju;
//     bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//         if (prerequisites.size() == 0) {
//             return true;
//         }
//         v.resize(numCourses);
//         ju.resize(numCourses, vector<int>(numCourses, 0));
//         vector<int> vis(numCourses, 0);
//         for (int i = 0; i < prerequisites.size(); i++) {
//             int a = prerequisites[i][0];
//             int b = prerequisites[i][1];
//             if (ju[a][b] == 1) {
//                 return false;
//             }
//             v[b].push_back(a);
//             ju[b][a] = 1;
//             vis[a]+=1;
//         }
//         queue<int> q;
//         for(int i=0;i<numCourses;i++)
//         {
//             if(vis[i]==0){
//                 q.push(i);
//             }
//         }
//         int sum=0;
//         while(!q.empty())
//         {
//             int t=q.front();
//             q.pop();
//             sum++;
//             for(auto& e:v[t])
//             {
//                 --vis[e];
//                 if(vis[e]==0){
//                     q.push(e);
//                 }
//             }
//         }
//         return sum==numCourses;
//     }
// };

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int size = prerequisites.size();
        vector<vector<int>> edge(numCourses);
        vector<int> count(numCourses, 0);
        for (int i = 0; i < size; i++) {
            edge[prerequisites[i][1]].push_back(prerequisites[i][0]);
            count[prerequisites[i][0]]++;
        }
        queue<int> q;
        int sum = 0;
        for (int i = 0; i < numCourses; i++) {
            if (!count[i])
                q.push(i);
        }
        while (!q.empty()) {
            int front = q.front();
            q.pop();
            ++sum;
            for (const auto& e : edge[front]) {
                if (--count[e] == 0)
                    q.push(e);
            }
        }
        return sum == numCourses;
    }
};